package 排序;

import java.util.Deque;
import java.util.LinkedList;

public class Sort {
    /**
     * 归并非递归
     */
    public static void mergeSortPlus(int[] array) {
        int gap = 1;
        while (gap<array.length) {
            for (int i = 0; i < array.length; i+=gap*2) {
               //left一定不会越界
                int left = i;
                //极端情况下
                //如果left==array.length-1
                //那么gap如果大于1就会越界
                int mid = left+gap-1;
                //防止越界
                //有可能越界
                if(mid>=array.length) {
                    mid=array.length-1;
                }
                int right = mid+gap;
                if(right>=array.length) {
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap*=2;
        }
    }
    /**
     * 归并排序
     * 时间复杂度：O(nlog(n))(不考虑优化)
     * 空间复杂度：O(n)
     * 稳定性:稳定
     */
    public static void mergeSort(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }
    private static void mergeSortFunc(int[] array, int left,int right ) {
        if(left>=right) {
            return;
        }
        int mid=left+(right-left)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);

    }
    //合并
    private static void merge(int[] array,int start,int end,int mid) {
        //如果start end mid 都一样，那么就相当于没交换
        if(start == end && end == mid) {
            return;
        }
        int s1 = start;
        int s2 = mid+1;
        int[] ret = new int[end-s1+1];
        int size = 0;
        //因为本身就是有序的数组合并，所以直接合并就行
        while (s1<=mid && s2<=end) {
            if(array[s1]<array[s2]) {
                ret[size++]=array[s1++];
            }else {
                ret[size++]=array[s2++];
            }
        }
        while (s1 <= mid) {
            ret[size++]=array[s1++];
        }
        while (s2 <= end) {
            ret[size++]=array[s2++];
        }
        for (int i = 0; i < ret.length; i++) {
            array[i+start]=ret[i];
        }
    }
    /**
     * 非递归实现快速排序
     */
    public static void quickSortPlus(int[] array) {
        Deque<Integer> stack =new LinkedList<>();
        int left=0;
        int right=array.length-1;
        int index = partition(array,left,right);
        if(left+1 < index) {
            stack.push(left);
            stack.push(index-1);
        }
        if(index+1 < right) {
            stack.push(index+1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
             left = stack.pop();
            index = partition(array,left,right);
            if(left+1 < index) {
                stack.push(left);
                stack.push(index-1);
            }
            if(index+1 < right) {
                stack.push(index+1);
                stack.push(right);
            }
        }
    }
    /**
     * 快速排序
     * 时间复杂度：
     * 最好：O(nlog(n))
     * 最坏：O(n^2)(不考虑优化)
     * 空间复杂度：
     * 最好：O(logN)
     * 最坏：O(N)(不考虑优化)
     * 稳定性:不稳定
     */
    public static void quickSort(int []array) {
        //找基准
        //递归
        //
        quick(array,0, array.length-1);
    }
    private static void quick(int[] array,int left ,int right) {
        if(left >= right) {
            return;
        }
        //如果区间内的结点数小于3，那就不继续递归了，直接插入
        if(right-left+1<=3) {
            InsertSort(array,left,right);
            return;
        }
        //优化
        int mid = ThreeMiddle(array,left,right);
        //三数取中法
        //然后和left交换
        swap(array,left,mid);
        int index = partition1(array,left,right);
        quick(array,left,index-1);
        quick(array,index+1,right);

    }
    //找基准（挖坑法）
    private static int partition(int[] array,int left, int right) {
        int tmp= array[left];
        while (left<right) {
            while (left<right&&array[right] >= tmp) {
                right--;
            }
            array[left]=array[right];
            while (left<right&&array[left] <= tmp) {
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    //找基准
    //Hoare法
    private static int partition1(int[] array,int left, int right) {
        int n = left;
        int tmp= array[left];
        while (left<right) {
            //为什么先走右边？
            while (left<right && array[right] >= tmp) {
                right--;
            }
            while (left<right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        //如果是先走左边，那么当left==right时，此时的array[left]=比tmp大的值
        //此时如果交换，就把比tmp大的值放左边了
        swap(array,n,left);
        return left;
    }
    //三数取中法
    private static int ThreeMiddle(int[] array,int left,int right) {
        int mid = left+(right-left)/2;
        //如果left>right 并且right>mid，那么中间的就是right
        if(array[left]>=array[right]) {
            if(array[right]>array[mid]) {
                return right;
            }
            //走到这里说明right<mid
            if(array[left]>array[mid]) {
                return mid;
            }else {
                //走到这里说明mid最大
                return left;
            }
            //如果right>left 并且left>mid，那么中间的就是left
        }else {
            if(array[left]>array[mid]) {
                return left;
            }
            if(array[right]>array[mid]) {
                return mid;
            }else {
                return right;
            }
        }
    }
    public static void InsertSort(int[]array,int left,int right) {
        for (int i = left+1; i <=right ; i++) {
            int tmp=array[i];
            int j=i-1;
            for ( ; j >=0 ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    /**
     * 冒泡排序
     * 时间复杂度：O(n^2)(不考虑优化)
     * 空间复杂度：O(1)
     * 稳定性:稳定
     */
     public static void BubbleSort(int[]array) {
         for (int i = 0; i < array.length; i++) {
             boolean flg=false;
             for (int j = 0; j < array.length-i-1 ; j++) {
                 if(array[j]>array[j+1]) {
                     swap(array,j,j+1);
                    flg=true;
                 }
             }
             if(!flg) {
                 return;
             }
         }
     }
    /**
     * 堆排序
     * 时间复杂度：O(nlog(n))
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void HeapSort(int []array) {
        //建堆
       // createBigHeap(array);
        int size= array.length-1;
        while (size>0) {
            swap(array,0,size);
            shiftDown(array,0,size);
            size--;
        }

    }
    //建立大根堆
   public static void createBigHeap(int[] array) {
        for (int i = (array.length-1-1)/2; i >=0 ; i--) {
            shiftDown(array,i,array.length);
        }
    }
    //向下调整
    private static void shiftDown (int[]array,int parent,int end) {
        int child = parent*2+1;
        while (child<end) {
            if(child+1 < end && array[child]<array[child+1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
            }else {
                break;
            }
            parent=child;
            child=child*2+1;
        }
    }
    /**
     * 选择排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void selectSort(int []array) {
        for (int i = 0; i <array.length ; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if(array[minIndex]>array[j]) {
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    /**
     * 希尔排序
     * 数据趋于有序排序速度很快
     * 时间复杂度：O(n^1.3~n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void ShellSort(int []array) {
        int gap=array.length;
        while (gap>1) {
            gap/=2;
            InsertSort(array,gap);
        }
        InsertSort(array);
    }
    public static void InsertSort(int[]array,int gap) {
        for (int i = gap; i <array.length ; i++) {
            int tmp=array[i];
            int j = i-gap;
            for ( ; j >=0 ; j-=gap) {
                if(array[j]>tmp) {
                    array[j+gap]=array[j];
                }else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    /**
     * 插入排序
     * 数据趋于有序排序速度很快
     * 建议在基本有序的数组使用插入排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     */
  public static void InsertSort(int[]array) {
      for (int i = 1; i <array.length ; i++) {
          int tmp=array[i];
          int j=i-1;
          for ( ; j >=0 ; j--) {
              if(array[j]>tmp) {
                  array[j+1]=array[j];
              }else {
                  break;
              }
          }
          array[j+1]=tmp;
      }
  }
    private static void swap(int[]array,int left,int right) {
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }
}
